/*
* leetcode 栈和排序
*
给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈
你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列
排列：指 1 到 n 每个数字出现且仅出现一次
数据范围：
1≤n≤5×10^4 ，排列中的值都满足 1≤val≤n

进阶：空间复杂度 O(n) ，时间复杂度 O(n)


* */
/*
* */
import java.util.*;
public class Solution {
    public int[] solve (int[] num) {
        int n=num.length,target=n,cnt=0;
        Deque<Integer> q=new ArrayDeque<>();
        Set<Integer> set=new HashSet<>();
        int[] ret=new int[n];
        for(int i=0;i<n;i++){
            if(num[i]==target){
                target--;
                ret[cnt++]=num[i];
                while(set.contains(target)){
                    set.remove(target);
                    target--;
                }
                while(!q.isEmpty()&&q.peek()>target){
                    ret[cnt++]=q.poll();
                }
            }else{
                q.push(num[i]);
                set.add(num[i]);
            }
        }
        while(!q.isEmpty()){
            ret[cnt++]=q.poll();
        }
        return ret;
    }
}